import sun.net.www.http.HttpCapture;

import javax.print.DocFlavor;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author : WXY
 * @create : 2022-08-19 21:22
 * @Info : 双链表实现栈和队列
 */
public class Code03_DoubleEndsQueueToStackAndQueue {
    public static class Node {
        public int value;
        public Node last;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public static class DoubleEndsQueue {
        public Node head;
        public Node tail;

        public void addFromHead(int value) {
            Node node = new Node(value);
            if (head == null) {
                head = node;
                tail = node;
            } else {
                node.next = head;
                head.last = node;
                head = node;
            }
        }

        public void addFromTail(int value) {
            Node node = new Node(value);
            if (head == null) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                node.last = tail;
                tail = node;
            }
        }

        public int popFromHaed() {
            if (head == null) return Integer.MIN_VALUE;
            Node cur = head;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = cur.next;
                cur.next = null;
                head.last = null;
            }
            return cur.value;
        }

        public int popFromBottom() {
            if (head == null) {
                return Integer.MIN_VALUE;
            }
            Node cur = tail;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
                cur.last = null;
            }
            return cur.value;
        }

        public boolean isEmpty() {
            return head == null;
        }
    }

    public static class MyStack {
        private DoubleEndsQueue queue;

        public MyStack() {
            queue = new DoubleEndsQueue();
        }

        public void push(int value) {
            queue.addFromHead(value);
        }

        public int pop() {
            return queue.popFromHaed();
        }

        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }

    public static class MyQueue {
        private DoubleEndsQueue queue;

        public MyQueue() {
            queue = new DoubleEndsQueue();
        }

        public void push(int value) {
            queue.addFromHead(value);
        }

        public int poll() {
            return queue.popFromBottom();
        }

        public boolean isEmpty() {
            return queue.isEmpty();
        }
    }

    public static boolean isEqual(int o1, int o2) {
//        if (o1 == null && o2 != null) {
//            return false;
//        }
//        if (o1 != null && o2 == null) {
//            return false;
//        }
//        if (o1 == null && o2 == null) {
//            return true;
//        }
        return o1 == o2;
    }

    public static void main(String[] args) {
        int oneTestDataNum = 100;
        int value = 19000;
        int testTime = 1000;
        for (int i = 0; i < testTime; i++) {
            MyStack myStack = new MyStack();
            MyQueue myQueue = new MyQueue();
            Stack<Integer> stack = new Stack<>();
            Queue<Integer> queue = new LinkedList<>();
            for (int j = 0; j < oneTestDataNum; j++) {
                int nums = (int) (Math.random() * value);
                if (stack.isEmpty()) {
                    myStack.push(nums);
                    stack.push(nums);
                } else {
                    if (Math.random() < 0.5) {
                        myStack.push(nums);
                        stack.push(nums);
                    } else {
                        if (!myStack.isEmpty() && !stack.isEmpty())
                            if (!isEqual(myStack.pop(), stack.pop().intValue())) {
                                System.out.println("oops1!");
                            }
                    }
                }
                int numq = (int) (Math.random() * value);
                if (stack.isEmpty()) {
                    myQueue.push(numq);
                    queue.offer(numq);
                } else {
                    if (Math.random() < 0.5) {
                        myQueue.push(numq);
                        queue.offer(numq);
                    } else {
                        if (!myQueue.isEmpty() && !queue.isEmpty())
                            if (!isEqual(myQueue.poll(), queue.poll().intValue())) {
                                System.out.println("oops2!");
                            }
                    }
                }
            }
        }
        System.out.println("finish!");
    }
}
